#include <boost/unordered_map.hpp>
#include <iostream>
#include <string>
using namespace std;

template <typename V>
struct LRUNode
{
    LRUNode() : prev(NULL), next(NULL) { }
    V value;
    LRUNode *prev;
    LRUNode *next;
};

template <typename K, typename V>
class LRUCache
{
    typedef LRUNode<V> node_type;
public:
    typedef K key_type;
    typedef V mapped_type;
    typedef pair<const key_type, node_type> value_type;
    LRUCache(int max) : m_max(max) {
        m_head.next = &m_tail;
        m_tail.prev = &m_head;
    }
    mapped_type &operator[](const key_type &k) {
        return update_or_insert(k).value;
    }
    void insert(const key_type &k, const mapped_type &v) {
        update_or_insert(k).value = v;
    }
private:
    node_type &update_or_insert(const key_type &k) {
        typename boost::unordered_map<key_type, node_type>::iterator it = m_map.find(k);
        node_type *node;
        if (it != m_map.end()) {
            node = &(it->second);
            /* remove */
            node->prev->next = node->next;
            node->next->prev = node->prev;
        } else {
            if (m_map.size() >= m_max) {
                /* remove last */
                cout << "remove " << m_tail.prev->value << endl;
                m_tail.prev = m_tail.prev->prev;
                m_tail.prev->next = &m_tail;
            }
        }
        /* move to head */
        node = &(m_map[k]);
        node->prev = &m_head;
        node->next = m_head.next;
        m_head.next->prev = node;
        m_head.next = node;
        return *node;
    }
    boost::unordered_map<key_type, node_type> m_map;
    node_type m_head;
    node_type m_tail;
    int m_max;
};

int main()
{
    LRUCache<int, string> cache(5);
    cache[1] = "111";
    cache[2] = "222";
    cache[3] = "333";
    cache[4] = "444";
    cache[5] = "555";
    cache[6] = "666"; /* remove 111 */
    cache[3] = "33333";
    cache[4] = "44444";
    cache[7] = "77777"; /* remove 222 */
    cache[8] = "88888"; /* remove 555 */
    cache[9] = "99999"; /* remove 666 */
    return 0;
}
